package LeetCode.month01.day29;

import java.util.ArrayList;
import java.util.List;

public class No679 {
    private static final double EPS = 1e-9;
    public boolean judgePoint24(int[] cards) {
        List<Double> list = new ArrayList<>();
        for (int i = 0; i < 4; i++) {
            list.add((double)cards[i]);
        }
        return dfs(list);
    }

    public static boolean dfs(List<Double> list){
        int n = list.size();
        if(n==1){
            return Math.abs(list.get(0)-24)<EPS;
        }
        for (int i = 0; i < n; i++) {
            double x = list.get(i);
            for (int j = i+1; j < n; j++) {
                List<Double> candidate = new ArrayList<>();
                double y = list.get(j);
                candidate.add(x+y);
                candidate.add(x-y);
                candidate.add(x*y);
                candidate.add(y-x);
                if(Math.abs(y)<EPS){
                    candidate.add(x/y);
                }
                if(Math.abs(x)<EPS){
                    candidate.add(y/x);
                }
                List<Double> newlist = new ArrayList<>(list);
                newlist.remove(j);
                for (Double v : candidate) {
                    newlist.set(i,v);
                    if(dfs(newlist)) return true;
                }
            }
        }
        return false;
    }
}
